FOCS 2022 | 高维设施选址问题基于几何哈希的数据流算法
关键词：数据流，高维欧氏空间，设施选址
导 读
本文是对已被 FOCS 2022 接收的 Streaming Facility Location in High Dimension Via Geometric Hashing 一文的解读。该工作由北京大学姜少峰课题组与英国、以色列、捷克等地学者合作完成，论文贡献者之一杨明炜为北京大学2019级图灵班本科生。论文聚焦于几何数据流算法设计在高维数据上的挑战，提出了新的基于几何哈希方法的算法框架，并将其应用在设施选址问题上，大幅改进了已有结果。
论文地址：
https://arxiv.org/abs/2204.02095
报告视频：
https://www.bilibili.com/video/BV1SB4y1v7mV?p=3
01
问题及背景
设施选址（Facility Location）是运筹学和计算机科学中的一个基本优化问题，无论是在理论研究还是在现实应用中都扮演着非常重要的角色。我们考虑欧氏空间下的一致设施选址（Uniform Facility Location, UFL）问题。在 UFL 中，输入为一个点集 ，要求选出一个设施集合 并在 中的每个点上以 的开设代价来开设一个设施, 目标是最小化总连接代价（ 中的每个点到距离其最近的设施的欧式距离之和）和设施开设代价之和，即找到 并最小化
其中 表示 点到 中的最近点的欧式距离。
几何数据流（geometric streaming）模型最早由 Indyk [4] 提出，并且 UFL 被认为是该模型下算法研究的基本问题之一。在几何数据流模型中，通常假定输入限制在 维的格点 内并以点的数据流的方式给出，算法需要在数据流结束时，针对数据流中所有的点组成的数据集给出输出。在该模型下，算法的性能主要以空间复杂度进行衡量，而记录问题的最优解的方案可能需要 位的空间。因此，我们要求算法输出问题的最优解的（近似）值，而不是给出具体的方案。具体来说，若一个问题的最优值为 OPT，那么我们称一个随机算法对该问题是 近似的（ ），如果其输出 以常数概率满足 。
我们聚焦于高维、 相对较大的情况，希望使用 的空间来得到 UFL 的近似。目前，几乎所有适用于高维的结果都是基于 quadtree/tree embedding 技术，而由于 tree embedding 的误差下界，这种技术只能做到 或者 近似比。因此，在高维空间下为一些基本的几何问题得到 甚至是 近似比成为了该领域的核心挑战之一，而这更要求算法设计技术上的创新。
02
结 果
对于几何数据流模型下的 UFL，我们创新地引入了一种基于几何哈希的方法，并将这种方法与重要性采样结合得到了一个全新的算法框架。该算法框架可以较为直接的在扫描两遍数据流的情况下实现，并得到一个 近似、 空间的算法。另外，我们还可以在只扫描一遍数据流、但要求数据流给出的顺序是均匀随机的情况下得到类似的空间和 近似比。这种 近似比是之前的 tree embedding/quadtree 技术即使使用两轮或者是假定随机顺序也不能得到的。最后，如果只允许扫描数据流一遍并假定数据流以任意顺序给出，我们仍得到了空间复杂度为 的 近似的算法。该近似比虽然达不到 ，但是也已经突破了 tree embedding 的下界，并且优于所有先前的适用于高维的 UFL 算法。
我们还给出了针对 UFL 的空间下界。我们证明了对任意维数 和 ，任何扫描数据流一遍且近似比优于1.085的算法都至少需要 的空间。这说明了使用 的空间得到 近似是不可能的。这本质上说明了 UFL 在高维下是显著难于低维情况的，因为 [2] 给出了一个 近似的使用 空间的算法。
03
算法技术
我们对 UFL 的估值基于 Mettu-Plaxton 算法 [6, 1] 给出的估计方法：对每个输入中的点 ，可以计算得到一个值 ，满足所有 之和是最优解的 近似，即 。因此我们只需要对 进行常数近似。
我们不介绍 的精确定义，而只讨论一个常数近似。为简便起见，从此我们假定开设代价 。对于每个 ，一个对于 的 近似值可以通过找到一个 使得 。这里对 ， 代表以 为球心半径为 的 维球。注意到 是随着 增大而减小的，而“ ”右边的 是递增的，因此这样的 是必然存在且唯一的。这个近似定义同时也给出了一种对于任何给定 计算 的数据流算法：只需要对每个 维护一个 的计数器即可在 空间内得到 的 近似。
回忆我们只需要对 进行估计。一个自然的想法是对 中的点进行均匀采样来得到无偏估计。然而，这里均匀采样可能需要巨大的样本量，其主要原因是可能有极少数的 具有较大的值并对 做出主要贡献，而其他非常多的 却只有接近于0、可忽略的值。下面的例子显示了这种情况（图1是一个示意）：令 ，其中 ， 中的点两两间距离至少为 ； ， 中的点两两间距离大致为 ； 和 的距离至少为 。此时对 ，有 ，且对 ，有 。因此 。为估计 OPT，必须采样到至少一个 中的点，而均匀采样采到 的概率只有 ，所以需要 个样本才能采到一个 的点，这是无法接受的。
图1. 一个使均匀采样需要巨大样本量的例子
3.1 基于几何哈希的重要性采样
一种解决的方法是使用重要性采样：以大致与 成比例的概率对每个点 进行采样。可以证明这样得到的无偏估计 具有较小的方差，结合 concentration 不等式可以在 次采样得到对于 十分精确的估计。然而，这里重要性采样并不能直接解决我们的问题，因为我们还是需要对 在 占比的某种有效估计，而使用重要性采样的目的正是为了估计 。
为了绕过对 的估值并使用重要性采样，我们创新地使用了一种几何哈希函数 。称所有哈希值相同的数据点的集合为一个 bucket，即对任意 ，称 为一个 bucket。我们首先将数据集 通过哈希映射到一个新点集 ，然后在哈希后的每个 bucket 上均匀采样，并从采到的 bucket 中均匀取出一个点 。依然考虑图1所示的例子。此时我们希望采到的 大概率是一个 的点。为此，我们要求哈希 将 的点分开映射到不同的 bucket，但将所有密集的 的点映射到很少的几个 bucket 上（如图2所示）。具体来说，我们考虑如下定义的哈希函数。
图2. 几何哈希函数的效果
定义
给定直径参数 ，我们称映射 是 gap， consistent 的，如果：
对任意 ，我们有 ，其中 表示集合 的直径；
对任意 满足 ，我们有 。
这种哈希函数是 Jia 等人首先提出的 [5]，并且最近在 Filtser 的工作 [3] 中得到了进一步研究。然而，将该哈希方法应用在数据流算法中尚属首次，并且之前的哈希函数的构造方法也并不适用于数据流模型。针对数据流模型，我们证明，对于任意维数 和直径参数 ，我们能够构造性地给出 gap， consistent 的哈希函数，且该哈希函数具有不依赖于输入数据和可被高效计算的特点。
对于之前的样例，若令 ，经过哈希映射后， 中的点被映射到不同的 bucket 中。而由于 ， 中的点总共被映射到 个不同的 bucket 中。如果使用之前提到的在 bucket 上进行的（两轮）均匀随机采样，大致只需要 的样本就可以采样到一个 中的点。
3.2 数据流算法的实现
接下来介绍如何把上述技术在数据流模型中实现。回忆我们需要先对 中的点进行重要性采样，再计算采样得到的点的 值。很自然地，可以通过扫描数据流第一遍来进行重要性采样，然后扫描第二遍来计算 ，从而得到一个扫描数据流两遍的算法。类似地，如果数据流中的点给出的顺序是随机的，那么算法可以使用前面一半的数据流进行采样，后面一半的数据流来计算 。
如果仅允许扫描数据流一遍且对输入顺序没有限制，算法将更为复杂。这里主要的挑战是无法直接对采样到的点 计算 的值，直观原因是由于 不是预先给定的因此无法知道应该对哪些 维护计数器。因此我们需要设计另外的统计量来帮助我们估计 。一个很重要的观察是，若哈希函数的每个 bucket 的直径足够小，那么当 bucket 中存在一个 较大的数据点时，bucket 内的所有数据点都有较大的 ，并且 bucket 内的数据点个数不会太多。因此，一个自然的想法是通过统计每一 bucket 内的数据点个数来判断 bucket 内的所有点都有较大的 还是较小的 。
但这么做的问题在于，有可能 bucket 内点的个数很少，但是其含有的 却仍然很小（注意这是与上述观察的相反方向），并且这会发生在 bucket 的边界包含了很多 较小的点的情况下，因此我们需要检测出这种情况。具体来说, 在统计 bucket 内数据点个数时，我们需要将 bucket 的边界适当增大，而为了保证边界增大后每个数据点被重复统计到的次数不会随 呈指数增长，我们需要利用几何哈希的 consistency 保证，且此时 gap 参数 限制了边界能够增大的最大距离。这种限制使得 gap 参数 直接影响算法的近似比——我们算法的近似比是 。最后，套用我们构造的 的几何哈希，可以得到 近似的算法。
04
未来工作展望
如上所述，我们针对任意顺序数据流、只进行单次扫描的算法的近似比是 。因此一种重要的未解问题是构造一个具有更小 gap 参数 的几何哈希来得到更好的近似比。另外，我们扫描数据流两遍即得到了常数近似比，那么能否通过扫描数据流更多遍来得到更好的近似比，例如 ？另一方面，我们的下界结果针对的是扫描一遍的数据流算法。一个很自然的问题是，这个下界能否被推广，例如针对扫描数据流多遍或者数据流的次序是随机给出的情况？
参考文献
[1] Mihai Badoiu, Artur Czumaj, Piotr Indyk, and Christian Sohler. Facility location in sublinear time. ICALP 2005.
[2] Artur Czumaj, Christiane Lammersen, Morteza Monemizadeh, and Christian Sohler. approximation for facility location in data streams. SODA 2013.
[3] Arnold Filtser. Scattering and sparse partitions, and their applications. ICALP 2020.
[4] Piotr Indyk. Algorithms for dynamic geometric problems over data streams. STOC 2004.
[5] Lujun Jia, Guolong Lin, Guevara Noubir, Rajmohan Rajaraman, and Ravi Sundaram. Universal approximations for tsp, steiner tree, and set cover. STOC 2005.
[6] Ramgopal R. Mettu and C. Greg Plaxton. The online median problem. SIAM J. Comput.,
32(3):816–832, 2003.
报告视频：
如自动跳转有误，请手动选择第三个视频
图文 | 杨明炜、姜少峰
PKU 姜少峰Lab
姜少峰课题组近期动态
— 版权声明 —
本微信公众号所有内容，由北京大学前沿计算研究中心微信自身创作、收集的文字、图片和音视频资料，版权属北京大学前沿计算研究中心微信所有；从公开渠道收集、整理及授权转载的文字、图片和音视频资料，版权属原作者。本公众号内容原作者如不愿意在本号刊登内容，请及时通知本号，予以删除。
点击“阅读原文”转论文链接